package com.gxc.dichotomy;

/**
 * 局部最小
 * Created by ASD on 2022/12/22.
 */
public class LocalMinimum {

    public static void main(String[] args) {
        int[] arr = new int[] {6,4,9,8,7,1,9};
        System.out.println(computeLocalMin(arr, 0, arr.length-1));
    }

    private static int computeLocalMin(int[] arr, int start, int end) {
        if (arr ==null | (end-start)==0) return -1;

        if (arr[start]<arr[start+1]) return arr[start];
        if (arr[end]<arr[end-1]) return arr[end];

        for (int i = start; i <= end; i++) {
            //int mid = (end+start)/2;
            int mid = start + ((end-start)>>1);
            if (arr[mid]<arr[mid-1] && arr[mid]<arr[mid+1]) return arr[mid];
            else if (arr[mid]<arr[mid-1]) {
                return computeLocalMin(arr, mid, end);
            } else {
                return computeLocalMin(arr, start, mid);
            }
        }
        return -1;
    }

}
